// 基数排序

const lower16 = function(num){
  return num & 0xffff;
}
const high16 = function(num){
  return (num & 0xffff0000) >> 16
}
/**
 * 思路： 
 * 先对低位排序，
 * 再对高位排序。 高位相等时，不改变排好的低位数据顺序。
 * 
 * 保证数据排序的稳定性，
 * 即，当前位相等时，不改变原来的数据顺序
 */

// 获取高位函数，不兼容负数
const radix_sort = function(arr){
  let n = arr.length;
  // cnt 记录每个值出现的个数， 下标代表arr的值，value代表出现个数
  let cnt = new Array(65536).fill(0);
  let temp = new Array(n);
  
  // 低16位排序
  /**
   * 计数
   * lower16(arr[i]) -- arr[i] 的低16位值
   * cnt[lower16(arr[i])] -- arr[i]出现的次数
   */
  for(let i = 0; i< n; i++) cnt[lower16(arr[i])] += 1;
  /**
   * cnt数组转为前缀和数组
   * cnt[lower16(arr[i])-1 -- 排序后arr[i]的最大下标
   */ 
  for(let i = 1; i < 65536; i++) cnt[i] += cnt[i - 1];
  /**
   * 放置到排序后的对应位置
   * 每遍历到一个值则将最大下标减1
   */ 
  for (let i = n - 1; i >= 0 ; i--) temp[--cnt[lower16(arr[i])]] = arr[i];

  // cnt复位
  for(let i = 0; i < 65535; i++) cnt[i] = 0;

  // 高16位
  // 计数
  for(let i = 0; i < n; i++) cnt[high16(temp[i])] += 1;
  // 转为前缀和
  for(let i = 1; i < 65535; i++) cnt[i] += cnt[i - 1];
  // 放置
  for(let i = n - 1; i >= 0; i--) arr[--cnt[high16(temp[i])]] = temp[i];
}
let arr = [1,4,38,8,6,4,3,10,39,22,9,45,3];

radix_sort(arr);
console.log(arr);